In recent years, computing systems have grown to large-scale distributed systems that use thousands of servers to process millions of file requests in a continuous and seamless high-speed fashion. In addition to being faster than past computer systems, these new distributed systems are also more robust because data items are replicated and stored at multiple physical locations. If the servers at one of the locations fail, servers at other locations can act as backups and redistribute data.
However, there remains a need to ensure that data in a distributed system is replicated correctly. For example, if an individual's bank account balance is stored as a data item at three geographically separate data centers and the individual deposits $100,000 into his/her account, ensuring that all three data centers reflect the updated value is of paramount importance. If the data message to “increase the bank account balance by $100,000” is received at only one of the three data centers, and is lost in transmission to the other two data centers, a data conflict occurs and it may be unclear which data center contains the correct value for the bank account data.
Various consensus based algorithms and protocols have been implemented in an attempt to solve data conflict problems. Generally, consensus algorithms, such as Paxos, work by requiring nodes (e.g. servers) to vote or arbitrate amongst themselves to form a consensus as to what the correct value is for a given piece of data. For example, in a five-node (e.g. five server) system, if three out of five nodes reflect a deposit update of $100,000, the three out of five nodes constitute a majority, and the remaining two out of five nodes will agree to also reflect the $100,000 update whether or not a message to update the account by $100,000 was received.
Though consensus algorithms may ensure higher data accuracy, they are computationally expensive because every data value that needs to be processed must be arbitrated and/or voted on multiple times, which creates additional network traffic for every update. Thus, many distributed systems are forced to balance speed versus accuracy.
As is evident, there is a need for an approach in distributed systems for data accuracy that does not come at the cost of sacrificing speed.